package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

// 一致性哈希

type Hash func(data []byte) uint32

type Map struct {
	hash     Hash
	replicas int            // 虚拟节点倍数
	keys     []int          // 哈希环
	hashMap  map[int]string // 虚拟节点与真实节点的映射表，k：虚拟节点的哈希值 v：真实节点的名称
}

// New Hash算法通过依赖注入的方式初始化，方便替换和测试
func New(replicas int, fn Hash) *Map {
	m := &Map{
		hash:     fn,
		replicas: replicas,
		hashMap:  make(map[int]string),
	}
	// 默认采用crc32.ChecksumIEEE算法
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}

	return m
}

func (m *Map) Add(keys ...string) {
	for _, key := range keys {
		for i := 0; i < m.replicas; i++ {
			// 虚拟节点的名称为：strconv.Itoa(i) + key
			// 根据节点名称计算虚拟节点的哈希值
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			m.keys = append(m.keys, hash)
			// 维护虚拟节点与真实节点的映射关系
			m.hashMap[hash] = key
		}
	}
	// 哈希值排序
	sort.Ints(m.keys)
}

func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		return ""
	}
	// 计算查询的key的hash值
	hash := int(m.hash([]byte(key)))
	// sort.Search会在[0,第一个参数)之间查找并返回符合第二个参数fn条件的最小的数
	// 计算第一个匹配的虚拟节点的下标
	idx := sort.Search(len(m.keys), func(i int) bool {
		// 顺时针遍历哈希环，第一个大于查询key的哈希值符合条件
		return m.keys[i] >= hash
	})

	// 通过虚拟节点插得到真实节点的名称
	// idx == len(m.keys)时，应选择m.key[0]，所以采用取余计算
	return m.hashMap[m.keys[idx%len(m.keys)]]
}
